package dynamic;

import java.util.Arrays;

/**
 * 构造最优二元搜索树
 * @author Linxiaozhi
 *
 */
public class OptimalBST {
	public static final int SIZE = 5;
	int n = SIZE;
	float[][] w = new float[n + 1][n + 1];
	float[] p = { 0, 0.15f, 0.10f, 0.05f, 0.10f, 0.20f };
	float[] q = { 0.05f, 0.10f, 0.05f, 0.05f, 0.05f, 0.10f };

	float[][] f = new float[n + 2][n + 1];
	int[][] a = new int[n + 1][n + 1];

	void dynamic() {
		for (int ii = 1; ii <= n; ii++) {
			f[ii][ii-1] = q[ii];
			w[ii][ii] = p[ii] + q[ii - 1] + q[ii];
			for (int len0 = 1; len0 <= n - ii; len0++) {
				int j = ii + len0;
				w[ii][j] = w[ii][j - 1] + p[j] + q[j];
			}
		}

		for (int len = 1; len <= n - 1; len++) {
			for (int i = 1; i <= n - len; i++) {				
				int j = i + len;			
				float min = Float.MAX_VALUE;
				int mink = 0;
				for (int k = i; k <= j; k++) {
					float temp = f[i][k - 1] + f[k + 1][j] + w[i][j];
					if (temp < min) {
						min = temp;
						mink = k;
					}
				}
				f[i][j] = min;
				a[i][j] = mink;
			}
		}
		System.out.println("---------------w--------------");
		printfa(w);
		System.out.println("---------------f--------------");
		printfa(f);
		System.out.println("---------------a--------------");
		printfa(a);

	}

	void printfa(float[][] f) {
		for (int i = 0; i < f.length; i++) {
			float[] t = f[i];
			for (int j = 0; j < t.length; j++) {
				System.out.printf("%-7.4f", f[i][j]);
			}
			System.out.println();
		}
	}

	void printfa(int[][] f) {
		for (int i = 0; i < f.length; i++) {
			int[] t = f[i];
			for (int j = 0; j < t.length; j++) {
				System.out.printf("%-7d", f[i][j]);
			}
			System.out.println();
		}
	}

	void output() {
		System.out.println("output:" + f[1][n]);
		outputA(1, n);
	}

	void outputA(int i, int j) {
		if (i - 1 == j) {
			System.out.print(i);
			return;
		} else if (i + 1 == j) {
			System.out.print(j);
			return;
		} else {
			int k = a[i][j];
			System.out.print("(");
			outputA(i, k - 1);
			System.out.print(")");
			System.out.print("(");
			outputA(k + 1, j);
			System.out.print(")");
		}
	}

	public static void main(String[] args) {
		OptimalBST ob = new OptimalBST();
		ob.dynamic();
		ob.output();
	}
}
